package com.itheima.datastructure.binarysearchtree.binarytree;

import com.itheima.datastructure.stack.LinkedListStack;

import java.util.LinkedList;

public class E08EspressionTree {
    /*后缀表达式建立二叉树
    建立思路：
    1.遇到数字直接入栈
    2.遇到运算符，建立节点关系，载入栈
     */

    static class TreeNode{
        public String val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(String val){
            this.val=val;
        }

        public TreeNode(String val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }

        @Override
        public String toString(){
            return  this.val;
        }
    }

    public TreeNode constructExpressionTree(String[] tokens){
        LinkedList<TreeNode> stack=new LinkedList<>();
        for(String t:tokens) {
            switch (t) {
                case "+", "-", "*", "/" -> { //运算符
                    TreeNode right = stack.pop();
                    TreeNode left = stack.pop();
                    TreeNode parent = new TreeNode(t);
                    parent.left=left;
                    parent.right=right;
                    stack.push(parent);
                }
                default -> {
                    //数字
                    stack.push(new TreeNode(t));
                }
            }
        }
        return stack.peek();
    }
}
